package com.mesnac.sort;

public class MaxHeapSort{ 
	
	public void maxHeapInsert(int a[],int i,int num){
		a[i] = num;
		maxHeapFixup(a,i);
	}
	private void maxHeapFixup(int a[], int i){
		int j = (i-1)/2;
		int temp = a[i];
		while(j >= 0 && i!= 0){
			if(a[j] >= temp)
				break;
			a[i] = a[j];
			i = j;
			j = (i-1)/2;
		}
		a[i] = temp;
	}
	public void maxHeapDel(int a[], int n){
		swap(a,0,n-1);
		maxHeapFixdown(a,0,n-1);
	}
	private void swap(int a[], int i ,int n){
		int temp = a[i];
		a[i] = a[n];
		a[n] = temp;
	}
	private void maxHeapFixdown(int a[],int i,int n){
		int j = i * 2 + 1;
		int temp = a[i];
		while(j < n){
			if(j+1 < n && a[j] < a[j+1])
				j++;
			if(a[j] <= temp)
				break;
			a[i] = a[j];
			i = j;
			j = i * 2 + 1;
			
		}
		a[i] = temp;	
	}
	//将一个数组调整成最大堆
	public void makeMaxHeap(int a[],int n){
		for(int i = n/2 -1; i >= 0 ;i--){
			maxHeapFixdown(a,i,n);
		}
	}
	//最大堆排序
	public void maxHeapSort(int a[],int n){
		for(int i = n-1; i >= 1; i--){
			swap(a,0,i);
			maxHeapFixdown(a,0,i);
		}
	}
	
	public static void main (String args[]){
		int a[] = {3,1,2,7,4,9,8,6,5,10};
		MaxHeapSort sort = new MaxHeapSort();
		sort.makeMaxHeap(a, 10);
		sort.maxHeapSort(a, 10);
		for(int i = 0; i < 10; i++){
			System.out.println(a[i]);
		}
	}
}
